The present invention relates generally to error detection and/or correction. More particularly, the invention relates to a physical or logical block address (PBA or LBA) transfer and recovery system and method for interleaved Reed-Solomon (RS) codes that can distinguish between a block address error and an uncorrectable data error and that permits recovery of the actual block address in the event of a physical or logical block address error.
Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The current trend is to store greater amounts of digital data in smaller areas on the storage medium. This trend increases the probability of errors. To correct the errors, error correction coding is used. There are various error correction coding techniques. One class of such error correction codes is the well-known Reed Solomon (RS) codes. The Reed Solomon (RS) encoding technique appends to each block of b user data symbols 2t redundancy symbols to create a codeword (where t represents the designed symbol error correcting capacity of the code). There are b+2t symbols in a RS codeword. The RS codewords are transmitted to and from the storage medium with a certain error probability. During the decoding phase, certain error patterns introduced from the transmission of the data from the storage medium can be detected and the original data reconstructed by analyzing the received data. See, for example, the reference xe2x80x9cError Control Systems for Digital Communication and Storage, by Stephen B. Wicker published 1995 by Prentice Hall, Inc., Englewood Cliffs, N.J. 07632, ISBN 0-13-200809-2, which is hereby incorporated by reference, for a discussion of some conventional error detection and control systems and methods.
Often errors occur in bursts rather than in random patterns, so that several consecutive bytes or symbols are in error. (In this description a symbols are used synonymously with bytes and it is understood that where the term byte is used, the number of bits is arbitrary and is not restricted to 8-bits, 16-bits or the like, but may take on any number of bits, for example 10 bits, 12 bits or other numbers.) If all the errors in such a burst are confined to a single codeword, the error correction coding technique may not be able to correct these errors, since the coding technique""s capacity is limited to correcting a predefined number of errors and the error burst may exceed this capacity. Interleaving is often used to overcome this problem. Interleaving is a technique that distributes user data symbols over several codewords so that the symbols from any given codeword are well separated during transmission. When the codewords are reconstructed during the decoding process, error bursts introduced during the transmission are broken up and spread across several codewords. The distribution of the errors in this manner is done so that the number of errors present in a codeword is more likely to be within the capacity of the error correction technique.
Encoded data is stored at a certain physical block address (PBA) on the storage medium. The PBA may also be associated with a particular Logical Block Address (LBA) so that references to PBAs in this discussion also apply to LBAs. Normally, each location on a recording media has a physical block address; however, since recording media such as magnetic discs, magneto-optical discs, magnetic tapes, and the like may have at least some imperfections, the media associated with some physical block addresses may be remapped to some different physical block addresses. Each of the available (error-free) physical block addresses is identified by a logical block address. In traditional systems and devices, the PBA (or LBA) can be used in the encoding/decoding process in such a way that if encoded data is decoded using a different PBA (or LBA), then the decoding process will fail, that is, the data will appear to have uncorrectable errors.
In one traditional approach, a disc drive computer system 100 having a host computer 102, a rotatable magnetic disc drive 104 having one or more discs for storing data thereupon, and a error correction code encoder/decoder unit (ECC encoder/decoder) 106 is provided as illustrated in FIG. 1 for the write or encoder operation. (A corresponding block diagram 101 for the readback or decoder operation is illustrated in FIG. 2 and described in greater detail hereinafter. ECC encoder/decoder 106 provides a first path between host 102 and disc 104 for user data D(x) 105 with only a multiplexer or switch 108 interposed between host 102 and disc 104, for selecting either data D(x) 105 or parity P(x) 107 as the information 109 to be written to disc 104. The manner in which data and parity are written to disc drive storage is well known in the art and not described further here. It is also understood that an actual implementation may include buffers, registers, clock signals, and other logic to implement the circuit, but being conventional are not described in order not to obscure the invention or its differences from traditional systems, devices, or methods.
A second path from host 102 to disc 104 is defined through syndrome/parity generator 110 which receives the output of exclusive-or (XOR) circuit 112 formed by the XOR of data D(x) and the output 113 of randomizer 116. Randomizer 116 receives the actual PBA (or LBA) 117 as a seed to generate a pseudo-random sequence output as is known in the art. Parity/syndrome generator 110 generates parity P(x) on the basis of the sum signal output by XOR 112. Multiplexer 108 selects or passes either data D(x) or parity P(x) in response to the state of a data/parity select control signal 119.
Randomizer unit 116 is important in the operation of the traditional ECC encoder/decoder unit 106 and is seeded with the intended or actual PBA value for writing (encoding) and with the expected or predicted PBA value 111 for readback (decoding). As described previously, the predicted or estimated PBA (or LBA) 111 may for example be a 4-byte value that specifies the location on the storage media, for example the track and sector on a magnetic disc, where the information is expected to be written to or read from. Seeding refers to a procedure for encoding or decoding in which the randomizer is preset with the value of the PBA (or LBA) prior to generating the pseudo-random sequence. The use of a seed to generate a pseudo-random sequence is well known in the art and not described further here.
The output sequence 113 of randomizer 116 is XOR""ed by XOR circuit 112 with the write data D(x) 105 arriving from host 102 for the parity generation during writing, and XOR""ed by XOR 112 with the read data D(x) 105 for the syndrome generation during readback (See FIG. 2 for readback configuration). In the read or readback mode of operation, data D(x) arrives from the disc 104 and is communicated to host 102 as illustrated in FIG. 2. The readback or decoder mode also employs an error correction unit (ECU) 120 which receives syndromes 121 generated by syndrome/parity generator 110 generates an uncorrectable error signal or indication 121 if the actual PBA (or LBA) is not equal to the expected PBA (or LBA) determines whether an error has occurred, but does not require the multiplexer 108 as the host has no need for parity and only receives the data D(x).
Unfortunately, if the seed values (in this case the PBA or LBA) used by randomizer 116 for write and readback operations of the same data are different, then the write output randomizer sequence and read output randomizer sequences will also be different and will not match or cancel each other as expected. Seeding values will be different, for example, if the estimated PBA (or LBA) is different from the actual PBA. When an error is detected, ECU 120 merely identifies that an uncorrectable error has occurred independent of whether the origin of the error is corrupted data, such as might be caused by media failure, or as a result of the actual PBA not matching the estimated PBA. In traditional systems no procedure is available for otherwise identifying the cause of the error as a wrong PBA.
This traditional approach therefore fails to solve all of the problems associated with error correction and wrong PBA and in particular does not allow one to distinguish between an uncorrectable data error and a wrong PBA. The traditional approach is also incapable of recover the actual PBA from the readback data.
It is desirable to distinguish between an uncorrectable data error and a wrong PBA (or LBA) for several reasons. First, a wrong PBA or LBA is of fundamentally different nature than a error caused, for example, by faulty media or the like. Second, it is useful to be able to recover the actual PBA or LBA from the readback data for adjusting the seek or synchronization operation of the disk drive during design of the control procedure. Finally, it may be advantageous in some high density recording systems where there may be a somewhat higher possibility that the portion of the disk read (PBA) is not the portion of the disk that should have been read, and to recover the actual PBA from the readback data to permit real-time or near-real-time adjustment of the seek operation control system. Therefore, a need exists for a solution to the problem of being able to distinguish between an uncorrectable data error and an wrong PBA or LBA, and a solution to the problem of being unable to recover the actual PBA or LBA from readback data.
The present invention provides a solution to this and other problems, and offers other advantages over the prior art.
The present invention relates to systems, devices, and methods that have a polynomial multiplier circuit operating on a prepended sequence derived from the storage device physical or logical block address and which provide an improved codeword stored on the media and which can distinguish an uncorrectable data error from a wrong block address error and permit the actual block address to be recovered from data read from the storage media in a data storage system to solve the above-mentioned problem.
In accordance with one embodiment of the invention, method for generating a parity symbol sequence of a code is provided in which a sequence representing an m-symbol address is received and a sequence of k data symbols is received. The sequence representing an m symbol address is multiplied by a set of multiplier symbols to generate a first sequence of product symbols that is equal to the sum of a first sequence and a second sequence wherein the last r coefficients (r is equal to the number of parity symbols) of the first sequence are zero and the degree of the second sequence is one less than the number of parity symbols. Then first sequence of product symbols is added to the data sequence prior to generating a first parity sequence for the sum of the data sequence plus the first sequence during a data transmission phase for the first k symbols of the codeword. Subsequently, the second sequence is added directly to the first parity sequence during a parity transmission phase for a number of symbols at the end of the codeword to generate the final parity sequence.
In accordance with another embodiment of the invention, the method for generating a parity symbol sequence of a code further includes generating a syndrome symbol sequence. Generating the syndrome symbol sequence involves receiving a sequence representing an m-symbol address estimation which may not be equal to the sequence representing the m-symbol address and a readback sequence of k+r data and parity symbols, some of which may be in error. Then the sequence representing the m-symbol address estimation is multiplied by a set of multiplier symbols to generate a second sequence of product symbols which will be identical to the first sequence of product symbols if m-symbol address estimation sequence is equal to the m-symbol address sequence. The second sequence of product symbols is also added to the readback sequence to generate a sum sequence, and syndromes are generated for the sum sequence.
Apparatus and system implementing the inventive method are also provided. For example, a data storage system for a computer system having the inventive features, such as may be provided for a rotating magnetic disc storage system, a magneto-optical storage system, a tape storage system, or any other data or information system when the address or location of the data may be in question. The inventive apparatus, system, and method may also be more generally applied to associate some form of auxiliary information (non-user data) other than address block information with user data so that errors in such auxiliary information may be identified and the auxiliary information recovered. The present invention also can be implemented as a computer-readable program storage device which tangibly embodies a program of instructions executable by a computer system to perform a block address error discrimination and recovery method. In addition, the invention also can be implemented as a block address error discrimination and recovery circuit itself, which circuit may be implemented as an element of a data storage system such as a disc drive system, which itself may for a constituent element of a computer system. Among its advantageous features, the invention provides physical block address and/or logical block address (PBA/LBA) recovery with virtual prepending in a headerless PBA/LBA integrity scheme.
These and various other features as well as advantages which characterize the present invention will be apparent upon reading of the following detailed description and review of the associated drawings.